/*
 * Copyright 北京航空航天大学  @ 2015 版权所有
 */
package com.buaa.edu.leetcode.algorithm.array;

import java.util.Arrays;

import org.junit.Test;

/**
 * <p>
 * 区间搜索，O(log(n))的时间复杂度 
 * If the target is not found in the array, return [-1, -1].
 * Given [5, 7, 7, 8, 8, 10] and target value 8, 
 * return [3, 4].
 * </p>
 * 
 * @author towan
 * @email tongwenzide@163.com
 * @time 2015年6月21日
 */
public class SearchForARange {

  public int[] searchRange(int[] nums, int target) {
      int []range = {-1,-1};
      int lower = 0;
      int upper = nums.length;
      int mid = 0;
      if(nums[upper-1]<target){
          return range;
      }
      //搜索起点
      while(lower<upper){
          mid = (lower+upper)/2;
          if(nums[mid]<target){
              //尽可能往目标值靠近
              lower = mid+1;
          }else{
              //不使用mid-1，因为要保留可能存在目标值的元素
              upper = mid;
          }
      }
      //如果目标值没有找到，则返回
      if(nums[lower]!=target){
          return range;
      }
      range[0] = lower;
      //搜索终点
      upper = nums.length;
      while(lower<upper){
          mid = (lower+upper)/2;
          if(nums[mid]>target){
              upper = mid;
          }else{
              lower = mid+1;
          }
      }
      range[1] = upper-1;
      return range;   
    }
  @Test
  public void testCase(){
      int []nums = {1,4};
      int[] searchRange = searchRange(nums, 4);
      System.out.println("Range:"+Arrays.toString(searchRange));
  }
}
